package 二叉树;
import java.util.*;
/**
 * 将有序数组转换为二叉搜索树
 * 时间复杂度O(n)，空间复杂度O(h)，n为节点个数，h为树的高度
 */
public class sortedArrayToBST {
    /**
     * 二叉树节点类
     * 包含节点值、左子节点和右子节点
     */
    public static class TreeNode{
        int val;            // 节点值
        TreeNode left;      // 左子节点
        TreeNode right;     // 右子节点
        
        // 无参构造函数
        TreeNode(){}
        
        // 带值的构造函数
        TreeNode(int val){
            this.val = val;
        }
        
        // 带值、左子节点和右子节点的构造函数
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 将有序数组转换为二叉搜索树
     * 使用递归方法构建二叉搜索树
     * 
     * @param nums 有序数组
     * @return 构建好的二叉搜索树根节点
     */
    public static TreeNode sortedArrayToBSTM(int[] nums){
        if(nums == null || nums.length == 0) return null; // 如果输入数组为空，返回null
        return convert(nums, 0, nums.length - 1); // 调用递归方法构建二叉搜索树
    }

    /**
     * 递归构建二叉搜索树
     * 
     * @param nums 有序数组
     * @param left 当前子数组的左边界
     * @param right 当前子数组的右边界
     * @return 构建好的二叉搜索树根节点
     */
    public static TreeNode convert(int[] nums, int left, int right){
        if(left > right) return null; // 如果左边界大于右边界，返回null
        int mid = (left + right) >> 1; // 计算中间索引
        TreeNode root = new TreeNode(nums[mid]); // 创建根节点
        root.left = convert(nums, left, mid - 1); // 递归构建左子树
        root.right = convert(nums, mid  + 1, right); // 递归构建右子树
        return root; // 返回构建好的根节点
    }

    /**
     * 层序遍历二叉树
     * 使用队列实现层序遍历，将节点值存入结果列表
     * 
     * @param root 二叉树的根节点
     * @return 层序遍历结果列表
     */
    public static List<Integer> levelOrder(TreeNode root){
        List<Integer> list = new ArrayList<>(); // 存储层序遍历结果
        if(root == null) return list; // 如果根节点为空，返回空列表
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root); // 将根节点加入队列
        while(!queue.isEmpty()){ // 当队列不为空时，继续遍历
            TreeNode cur = queue.poll(); // 取出队首节点
            list.add(cur.val); // 将当前节点值加入结果列表
            if(cur.left != null) queue.offer(cur.left); // 将左子节点加入队列
            if(cur.right != null) queue.offer(cur.right); // 将右子节点加入队列
        }
        return list; // 返回层序遍历结果
    }

    /**
     * 序列化二叉树
     * 将二叉树转换为字符串表示
     * 
     * @param root 二叉树的根节点
     * @return 序列化后的字符串列表
     */
    public static List<String> serialize(TreeNode root){
        List<String> list = new ArrayList<>(); // 存储序列化结果
        if(root == null) return list; // 如果根节点为空，返回空列表
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root); // 将根节点加入队列
        list.add(Integer.toString(root.val)); // 将根节点值加入结果列表
        while(!queue.isEmpty()){ // 当队列不为空时，继续遍历
            TreeNode cur = queue.poll(); // 取出队首节点
            if(cur.left != null){ // 如果左子节点不为null
                list.add(Integer.toString(cur.left.val)); // 将左子节点值加入结果列表
                queue.offer(cur.left); // 将左子节点加入队列
            }else{
                list.add("null"); // 如果左子节点为null，加入"null"
            }
            if(cur.right != null){ // 如果右子节点不为null
                list.add(Integer.toString(cur.right.val)); // 将右子节点值加入结果列表
                queue.offer(cur.right); // 将右子节点加入队列
            }else{
                list.add("null"); // 如果右子节点为null，加入"null"
            }
        }
        int last = list.size() - 1; // 获取结果列表的最后一个索引
        for(int i = last; i >= 0; i--){ // 从后向前遍历结果列表
            if(list.get(i).equals("null")) // 如果当前元素为"null"
                list.remove(i); // 移除该元素
            else
                break; // 否则退出循环
        }
        return list; // 返回序列化后的字符串列表
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用逗号分隔，表示有序数组
     * 例如：1,2,3,4,5 表示一个有序数组
     * 输出格式：构建的二叉搜索树的层序遍历结果和序列化结果
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] nodes = sc.nextLine().split(","); // 读取输入并分割
        int[] nums = new int[nodes.length]; // 创建数组
        for(int i = 0; i < nodes.length; i++){ // 将输入转换为整数数组
            nums[i] = Integer.parseInt(nodes[i]); // 将字符串转换为整数
        }
        TreeNode root = sortedArrayToBSTM(nums); // 构建二叉搜索树
        List<Integer> result = levelOrder(root); // 层序遍历二叉搜索树
        List<String> res = serialize(root); // 序列化二叉搜索树
        System.out.println(result); // 输出层序遍历结果
        System.out.println(res); // 输出序列化结果
        sc.close(); // 关闭输入流
    }
}
